A computer system can be broken into three basic blocks: a central processing unit (CPU), memory, and input/output (I/O) units. These blocks are interconnected by means of a bus. An input device such as a keyboard, mouse, disk drive, etc., is used to input instructions and data to the computer system via the I/O unit. These instructions and data can be stored in memory. The CPU retrieves the data stored in the memory and processes the data as directed by the stored instructions. The results can be stored back into memory or outputted via the I/O unit to an output device such as a printer, cathode-ray tube (CRT) display, liquid crystal display (LCD), etc.
In some computer systems multiple processors are utilized. This use of multiple processors allows various tasks or functions to be handled by other than a single CPU so that the computing power of the overall system is enhanced. In some currently available systems, up to four processors are connected with a single shared bus. In such multiprocessor systems, two or more processors may request a shared resource (for example, the same cache line) at the same time. Current multiprocessor systems with a single shared bus commonly resolve contention between processors for the same resource by the “order of operations.” In other words, the processors are granted the shared resource in the order that the bus transaction requests occur.
However, certain architectures do not permit multiple bus transactions to be outstanding for a single shared resource. In these architectures, the processor that initiated the transaction “first” is allowed to complete the transaction. All subsequent transactions are retried if the transactions are for the same resource and the transactions occur before the first transaction has completed. A transaction may be retried any number of times until the transaction is allowed to complete. However, a problem arises when one processor is “locked out” because it is always being retried.
For example, such a problem can occur when multiple processors initiate bus transactions for the same resource at about the same time and the first processor that is granted the resource is only reading the resource. In this case, a live-lock situation can occur if a subsequent bus transaction for the same resource is to modify the resource and that subsequent bus transaction is continually retried. Even though the subsequent bus transaction to modify the resource is retried, the other processors still snoop the subsequent bus transaction. The first processor's cache memory contains a copy of the resource as a result of the read operation. However, the first processor's copy of the resource is then invalidated when the first processor snoops the subsequent bus transaction to modify the resource. This causes the first processor to issue another bus transaction to acquire a valid copy of the same resource. Live-lock occurs when the first processor that is just reading the resource is always being granted the resource and a second processor that is trying to modify the resource is continually being retried.
Such a live-lock situation can cause a temporary stall and lack of forward progress in a program. The possibility of a processor stalling increases as more processors are added to a system. Clearly, from a performance standpoint, this is a highly undesirable situation.
Thus, there is a need for a mechanism to prevent live-lock in a multiprocessor system.